1. Field of the Invention
The present invention generally relates to digital halftoning as applied to laser printers or xerographic printers and, more particularly, to a method to correct and/or adjust the undesirable patterns generated by multicell clustered dither threshold arrays by using aperiodicity to increment from one acceptable pattern to the next.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots of a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance.
The fastest and most commonly used methods for digital halftoning are dithering algorithms which use threshold arrays. The original forms of these arrays used periodic patterns of threshold values which can have an unpleasant rendering at certain gray levels. The method described here can eliminate or reduce unpleasant patterns by introducing blue noise generated via a potential method in the determination of threshold locations for these intermediate patterns.
Too much randomness in the design of a dither array blurs the image and yields unesthetic results. Based on the discovery that blue noise, or noise with the low frequencies attenuated, gives the best visual effect, as described for instance by R. Ulichney in "Dithering with blue noise", Proc. IEEE, 76, No. 1 (1988), pp. 56-79, methods to construct dithering masks with blue noise were proposed for instance in U.S. Pat. No. 5,111,310 to K. J. Parker and T. Mitsa, by M. Yao and K. J. Parker in "Modified approach to the construction of a blue noise mask", J. of Eledtronic Imaging, 3, No.1 (1994), pp. 92-97, and by R. Ulichney in "The Void-and-Cluster Method for Dither Array Generation", Proc. SPIE, 1913 (1993), pp. 332-343.
However, such blue noise masks generate dispersed dots. As a consequence, they are not practical for laser printers or xerographic printers where one needs to cluster the black dots to improve both the fidelity and the control of the dot overlaps, and to cluster the white dots to ensure their visibility (at least in the dark areas).
To achieve clustering, one uses a traditional threshold array constructed so that increasing the grey level corresponds to printing larger and larger clusters at a fixed periodicity. This method does not produce unpleasant artifacts, but the number of grey levels that can be represented is often too small, especially when the cluster period is also small. To correct this effect, one usually uses a multicell array, which includes several single-cluster threshold arrays. In a multicell array, several clusters are grown with the same spatial period as in the single-cluster array, but are not grown simultaneously with each other. This allows for additional intermediate grey levels. The order and manner in which the clusters are grown commonly produce unpleasant artifacts at certain grey levels.
Most of these techniques and others are reviewed in the book by R. Ulichney entitled Digital Halftoning, (MIT Press, Cambridge, Mass. 1987), which is a general reference for digital halftoning.